What is a Spanning Tree?

Now that we have formalized the components of a connected graph, let's explore a special kind of subgraph we can derive from it: a spanning tree. This structure is the foundation for solving network optimization problems.

A spanning tree must span the graph, meaning it connects all of the original vertices from $V$.
It must be a tree, which means it has no cycles. A cycle is a path that starts and ends at the same vertex without reusing edges.
For a graph with $V$ vertices, any spanning tree will have exactly $V-1$ edges. Adding one more edge creates a cycle, and removing one disconnects it.

Spanning Tree

For a given connected, undirected graph $G = (V, E)$, a spanning tree $T$ is a subgraph $T = (V, E')$ where $E' \subseteq E$ such that $T$ is connected and acyclic. For a graph with $V$ vertices, any spanning tree $T$ must contain exactly $|E'| = V-1$ edges.